/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
// 与39不同的是：同层如果相等直接找一个数，只跟前面的比
// 比如第一层 1 1 2 5 6 7 10，选第一个1后不能选第二个1
// 易错点：如果直接candidates[j] !== candidates[j - 1]，由于candidates是共享的，所以第二层会丢掉1
// 解决：只跟当前数前面，进入第二层第二个1是首位它前面并没有数，所以用 j  > i
var combinationSum2 = function (candidates, target) {
    const ans = []
    let path = [], len = candidates.length
    // 对数组排序，方便去重
    candidates.sort((a ,b) => a - b)
    const backtracking = (i, target) => {
        if (target < 0) return
        if (target == 0) {
            ans.push(JSON.parse(JSON.stringify(path)))
            return
        }
        for (let j = i; j < len; j++) {
            if(j > i && candidates[j] == candidates[j - 1]) continue
            path.push(candidates[j])
            backtracking(j + 1, target - candidates[j])
            path.pop()
        }
    }
    backtracking(0, target)
    return ans
};
console.log(combinationSum2([10,1,2,7,6,1,5], 8));